package dailyTopic;

import java.util.Arrays;

/**
 * @author zhangmin
 * @create 2021-08-02 14:49
 */
public class networkDelayTime743 {
    int INF = 0x3f3f3f3f;

    void dijkstra(int[][] w,int k,int n,int[] d) {
        boolean[] visied = new boolean[n+1];
        Arrays.fill(visied, false);
        d[k]=0;
        for (int p = 1; p <=n ; p++) {
            int t=-1;//记录前驱节点
            for (int j=1;j<=n;j++){
                if (!visied[j]&&(t==-1||d[j]<d[t]))
                    t=j;
            }
            visied[t]=true;
            for (int i=1;i<=n;i++){
                d[i]=Math.min(d[i],d[t]+w[t][i]);
            }
        }
    }
    public int networkDelayTime(int[][] times, int n, int k) {
        //d用来存储k到每个点的最短路径的值
        int[] d=new int[n+1];
        Arrays.fill(d,INF);
        //使用邻接矩阵存
        int[][] w=new int[n+1][n+1];
        for (int i = 1; i <=n ; i++) {
            for (int j = 1; j <=n ; j++) {
                if (i==j){
                    w[i][j]=w[j][i]=0;
                }else {
                    w[i][j]=w[j][i]=INF;
                }
            }
        }
        //w[0][0]=INF;
        for (int[] t:times) {
            int u=t[0],v=t[1],c=t[2];
            w[u][v]=c;
        }

        dijkstra(w,k,n,d);
        int res=0;
        for (int i = 1; i <=n ; i++) {
            res=Math.max(res,d[i]);
        }
        return res>INF/2?-1:res;
    }

    /*public static void main(String[] args) {
        //int[] nums1=new int[]{3,5,4,2,4,6};
        //int[] nums2=new int[]{2,3,5};
        int[][] times=new int[][]{{2,1,1},{2,3,1},{3,4,1}};
        // String columnTitle = "AB";
        dailyTopic.networkDelayTime743 object=new dailyTopic.networkDelayTime743();
        System.out.println(object.networkDelayTime(times,4,2));
        *//*for (int r:res) {
            System.out.println(r);
        }*//*

    }*/
}
